//package leetcode;
//
//class Solution {
//    public void quick_sort(int[] arr, int begin, int end) {
//        if (begin >= end) {
//            return;
//        }
//        int left = begin;
//        int right = end;
//        int key = left;
//        while (left < right) {
//            while (left < right && arr[right] >= arr[key]) {
//                right--;
//            }
//            while (left < right && arr[left] <= arr[key]) {
//                left++;
//            }
//            if (left < right) {
//                swap(arr, left, right);
//            }
//        }
//        int meet = left;
//        swap(arr, key, meet);
//
//        quick_sort(arr, begin, meet - 1);
//        quick_sort(arr, meet + 1, end);
//
//    }
//
//    private void swap(int[] arr, int left, int right) {
//        int tmp = arr[left];
//        arr[left] = arr[right];
//        arr[right] = tmp;
//    }
//}
//
//public class Test2S {
//    public static void main(String[] args) {
//        Solution solution = new Solution();
//        int[] arr = {1, 2, 5, 9, 5, 63, 3};
//        solution.quick_sort(arr, 0, arr.length - 1);
//        for (Integer i : arr) {
//            System.out.print(i + " ");
//        }
//    }
//}
